package code.starivan.leetcode;

import code.starivan.leetcode.common.TreeNode;

/**
 * Created by Ivan on 2015/10/21.
 */
/*
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

        An example is the root-to-leaf path 1->2->3 which represents the number 123.

        Find the total sum of all root-to-leaf numbers.

        For example,

        1
        / \
        2   3
        The root-to-leaf path 1->2 represents the number 12.
        The root-to-leaf path 1->3 represents the number 13.

        Return the sum = 12 + 13 = 25.
*/

public class N129_SumRoottoLeafNumbers {
    public static void test(){
        TreeNode n1=new TreeNode(1);
        TreeNode n2=new TreeNode(2);
        TreeNode n3=new TreeNode(3);

        n1.left=n2;
        n1.right=n3;

        System.out.println(new N129_SumRoottoLeafNumbers().sumNumbers(n1));
    }

    public int sumNumbers(TreeNode root) {
        int[] ret=new int[]{0};
        int base=0;
        count(root,base,ret);
        return ret[0];
    }

    private void count(TreeNode node,int base,int[] ret){
        if(node==null){
            return;
        }

        int next=base*10+node.val;
        if(node.left==null&&node.right==null){
            ret[0]+=next;
        }else{
            count(node.left,next,ret);
            count(node.right,next,ret);
        }
    }
}
